/*
 * Copyright (c) 2022 Hong Jiahua
 * https://gitee.com/arrco/jh_vector
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef __JH_VECTOR_H__
#define __JH_VECTOR_H__

/************************************************************************/
/*                                                                      */
/************************************************************************/
#include <stdlib.h>

#define jh_vector_malloc    malloc
#define jh_vector_realloc   realloc
#define jh_vector_free      free

#include <string.h>

#define jh_vector_memcpy    memcpy
#define jh_vector_memmove   memmove

#ifdef __GNUC__
#define jh_vector_autofree __attribute__((cleanup(jh_vector_freespace)))
__attribute__ ((always_inline))
inline void jh_vector_freespace(void *ptr) {
    void *dataptr = *(void **)(ptr);
    if(dataptr)
        jh_vector_free(dataptr);
}
#else
#define jh_vector_autofree
#endif

#define __JH_VECTOR_COUNT_ARGSCOUNT_ARGS(_0, _1, _2, _3, _4, _5, _n, X...) _n
#define JH_VECTOR_COUNT_ARGS(X...) __JH_VECTOR_COUNT_ARGSCOUNT_ARGS(, ##X, 5, 4, 3, 2, 1, 0)

#define __JH_VECTOR_CONCATL(a, b) a ## b
#define JH_VECTOR_CONCATENATEL(a, b) __JH_VECTOR_CONCATL(a, b)

#define JH_VECTOR_INIT_CAPACITY 8

#define JH_VECTOR_DISABLE_ROUNDUP_POW_OF_TWO    0

#if JH_VECTOR_DISABLE_ROUNDUP_POW_OF_TWO
#define jh_vector_roundup_pow_of_two(_val) (_val)
#else
#if (__WORDSIZE == 64)
#define jh_vector_roundup_pow_of_two(_val) (--(_val), (_val)|=(_val)>>1, (_val)|=(_val)>>2, (_val)|=(_val)>>4, (_val)|=(_val)>>8, (_val)|=(_val)>>16, (_val)|=(_val)>>32, ++(_val), (_val))
#else
#define jh_vector_roundup_pow_of_two(_val) (--(_val), (_val)|=(_val)>>1, (_val)|=(_val)>>2, (_val)|=(_val)>>4, (_val)|=(_val)>>8, (_val)|=(_val)>>16, ++(_val), (_val))
#endif
#endif

#define jh_vector_global_type(_type) struct { _type *data; size_t num, capacity; }
#define jh_vector_type(_type) jh_vector_autofree struct { _type *data; size_t num, capacity; }

#define jh_vector_global_type_name(_type, _name) struct { _type *data; size_t num, capacity; } _name = { .data = 0, .num = 0, .capacity = 0, }
#define jh_vector_type_name(_type, _name) jh_vector_autofree jh_vector_global_type_name(_type, _name)

#define jh_vector_init_1(_vector)  ((_vector).num = 0, (_vector).capacity = JH_VECTOR_INIT_CAPACITY, (_vector).data = jh_vector_malloc(sizeof(*(_vector).data) * JH_VECTOR_INIT_CAPACITY))
#define jh_vector_init_2(_vector, _n)  ((_vector).num = (_n), (_vector).capacity = (_vector).num ? : JH_VECTOR_INIT_CAPACITY, (_vector).capacity = jh_vector_roundup_pow_of_two((_vector).capacity), (_vector).data = jh_vector_malloc(sizeof(*(_vector).data) * (_vector).capacity))
#define jh_vector_init_3(_vector, _n, _value)   do {                                                                        \
                                                    size_t _jh_n = (_n);                                                    \
                                                    jh_vector_init_2(_vector, _jh_n);                                       \
                                                    int _jh_i = 0;                                                          \
                                                    for(_jh_i = 0; _jh_i < _jh_n; _jh_i++)(_vector).data[_jh_i] = _value;   \
                                                } while(0)
#define jh_vector_init(...) JH_VECTOR_CONCATENATEL(jh_vector_init_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_reinit_2(_vector, _n)    ((_vector).num = (_n), (_vector).capacity = (_vector).num ? : JH_VECTOR_INIT_CAPACITY, (_vector).capacity = jh_vector_roundup_pow_of_two((_vector).capacity), (_vector).data = jh_vector_realloc((_vector).data, sizeof(*(_vector).data) * (_vector).capacity))
#define jh_vector_reinit_3(_vector, _n, _value) do {                                                                        \
                                                    size_t _jh_n = (_n);                                                    \
                                                    jh_vector_reinit_2(_vector, _jh_n);                                     \
                                                    int _jh_i = 0;                                                          \
                                                    for(_jh_i = 0; _jh_i < _jh_n; _jh_i++)(_vector).data[_jh_i] = _value;   \
                                                } while(0)
#define jh_vector_reinit(...) JH_VECTOR_CONCATENATEL(jh_vector_reinit_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_interior_reserve(_vector, _n) ((_vector).capacity = (_n), (_vector).capacity = jh_vector_roundup_pow_of_two((_vector).capacity), (_vector).data = jh_vector_realloc((_vector).data, sizeof(*(_vector).data) * (_vector).capacity))

#define jh_vector_resize_2(_vector, _n, ...)    do {                                                            \
                                                    (_vector).num = (_n);                                       \
                                                    if((_vector).num >= (_vector).capacity) {                   \
                                                        jh_vector_interior_reserve((_vector), (_vector).num);   \
                                                    }                                                           \
                                                } while(0)
#define jh_vector_resize_3(_vector, _n, _value) do {                                                                                \
                                                    size_t _jh_n = (_n), _old_num = (_vector).num;                                  \
                                                    jh_vector_resize_2(_vector, _jh_n);                                             \
                                                    int _jh_i = 0;                                                                  \
                                                    for(_jh_i = _old_num; _jh_i < _jh_n; _jh_i++)(_vector).data[_jh_i] = _value;    \
                                                } while(0)
#define jh_vector_resize(...) JH_VECTOR_CONCATENATEL(jh_vector_resize_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_reserve(_vector, _n)  do {                                                    \
                                            size_t _jh_n = (_n);                                \
                                            if(_jh_n > (_vector).capacity) {                    \
                                                jh_vector_interior_reserve((_vector), _jh_n);   \
                                            }                                                   \
                                        } while(0)

#define jh_vector_destroy(_vector) (jh_vector_free((_vector).data), (_vector).data = NULL)
#define jh_vector_at(_vector, _i) ((_vector).data[(_i)])

#define jh_vector_data_1(_vector) (&((_vector).data[0]))
#define jh_vector_data_2(_vector, _i) (&((_vector).data[(_i)]))
#define jh_vector_data(...) JH_VECTOR_CONCATENATEL(jh_vector_data_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_struct_at(_vector, _i, _name) ((_vector).data[(_i)]._name)
#define jh_vector_struct_data(_vector, _i, _name) (&((_vector).data[(_i)]._name))

#define jh_vector_front(_vector) ((_vector).data[0])
#define jh_vector_back(_vector) ((_vector).data[((_vector).num ? (_vector).num - 1 : 0)])

#define jh_vector_begin(_vector) (0)
#define jh_vector_end(_vector) ((_vector).num)

#define jh_vector_size(_vector) ((_vector).num)
#define jh_vector_capacity(_vector) ((_vector).capacity)
#define jh_vector_clear(_vector)  ((_vector).num = 0)
#define jh_vector_empty(_vector)  ((_vector).num == 0)
#define jh_vector_full(_vector)  ((_vector).num == (_vector).capacity)
#define jh_vector_pop_back(_vector)  ((_vector).num ? (_vector).data[--(_vector).num] : (_vector).data[(_vector).num])
#define jh_vector_push_back(_vector, _value) do {                                                                                                       \
                                                if ((_vector).num == (_vector).capacity) {                                                              \
                                                    (_vector).capacity = (_vector).capacity ? (_vector).capacity << 1 : JH_VECTOR_INIT_CAPACITY;        \
                                                    (_vector).data = jh_vector_realloc((_vector).data, sizeof(*(_vector).data) * (_vector).capacity);   \
                                                }                                                                                                       \
                                                ((_vector).data[(_vector).num++]) = (_value);                                                           \
                                            } while(0)
#define jh_vector_modify_3(_vector, _i, _value) do {                                                                        \
                                                    size_t _jh_i = (_i);                                                    \
                                                    if (_jh_i >= (_vector).capacity) {                                      \
                                                        (_vector).num = (_jh_i + 1);                                        \
                                                        jh_vector_interior_reserve((_vector), (_vector).num);               \
                                                    } else {                                                                \
                                                        (_vector).num = _jh_i >= (_vector).num ? _jh_i + 1 : (_vector).num; \
                                                    }                                                                       \
                                                    ((_vector).data[_jh_i]) = (_value);                                     \
                                                } while(0)
#define jh_vector_modify_4(_vector, _first, _last, _value) do {                                                                                             \
                                                            size_t _jh_begin = (_first), _jh_end = (_last);                                                 \
                                                            if (_jh_end > (_vector).capacity) {                                                             \
                                                                (_vector).num = _jh_end;                                                                    \
                                                                jh_vector_interior_reserve((_vector), (_vector).num);                                       \
                                                            } else {                                                                                        \
                                                                (_vector).num = _jh_end > (_vector).num ? _jh_end : (_vector).num;                          \
                                                            }                                                                                               \
                                                            int _jh_i = 0; for(_jh_i = _jh_begin; _jh_i < _jh_end; _jh_i++)(_vector).data[_jh_i] = _value;  \
                                                        } while(0)
#define jh_vector_modify(...) JH_VECTOR_CONCATENATEL(jh_vector_modify_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_insert_3(_vector, _position, _value)  do {                                                                    \
                                                            size_t _jh_position = (_position);                                  \
                                                            if(_jh_position < (_vector).num) {                                  \
                                                                if((_vector).num == (_vector).capacity) {                       \
                                                                    jh_vector_interior_reserve((_vector), ((_vector).num + 1)); \
                                                                }                                                               \
                                                                jh_vector_memmove((_vector).data + _jh_position + 1, (_vector).data + _jh_position, sizeof(*(_vector).data) * (((_vector).num++) - _jh_position));  \
                                                                (_vector).data[_jh_position] = (_value);                        \
                                                            } else {                                                            \
                                                                if (_jh_position >= (_vector).capacity) {                       \
                                                                    jh_vector_interior_reserve((_vector), (_jh_position + 1));  \
                                                                }                                                               \
                                                                (_vector).num = _jh_position + 1;                               \
                                                                ((_vector).data[_jh_position]) = (_value);                      \
                                                            }                                                                   \
                                                        } while(0)
#define jh_vector_insert_4(_vector, _position, _n, _value)  do {                                                                                                \
                                                                size_t _jh_position = (_position), _jh_n = (_n);                                                \
                                                                if(_jh_position < (_vector).num) {                                                              \
                                                                    if ((_vector).num + _jh_n > (_vector).capacity) {                                           \
                                                                        jh_vector_interior_reserve((_vector), ((_vector).num + _jh_n));                         \
                                                                    }                                                                                           \
                                                                    jh_vector_memmove((_vector).data + _jh_position + _jh_n, (_vector).data + _jh_position, sizeof(*(_vector).data) * ((_vector).num - _jh_position));  \
                                                                    (_vector).num += _jh_n;                                                                     \
                                                                    int _jh_i;                                                                                  \
                                                                    for(_jh_i = _position; _jh_i < (_position + _jh_n); _jh_i++)(_vector).data[_jh_i] = _value; \
                                                                } else {                                                                                        \
                                                                    if (_jh_position + _jh_n > (_vector).capacity) {                                            \
                                                                        jh_vector_interior_reserve((_vector), (_jh_position + _jh_n));                          \
                                                                    }                                                                                           \
                                                                    (_vector).num = _jh_position + _jh_n;                                                       \
                                                                    int _jh_i;                                                                                  \
                                                                    for(_jh_i = _position; _jh_i < (_position + _jh_n); _jh_i++)(_vector).data[_jh_i] = _value; \
                                                                }                                                                                               \
                                                            } while(0)
#define jh_vector_insert_5(_vector1, _position, _vector2, _first, _last)    do {                                                                                                                            \
                                                                                size_t _jh_position = (_position), _jh_first = (_first), _jh_last = (_last), _jh_n;                                         \
                                                                                if(_jh_first < (_vector2).num) {                                                                                            \
                                                                                    _jh_last = _jh_last > (_vector2).num ? (_vector2).num : _jh_last;                                                       \
                                                                                    _jh_n = _jh_last - _jh_first;                                                                                           \
                                                                                    if(_jh_position < (_vector1).num) {                                                                                     \
                                                                                        if ((_vector1).num + _jh_n > (_vector1).capacity) {                                                                 \
                                                                                            jh_vector_interior_reserve((_vector1), ((_vector1).num + _jh_n));                                               \
                                                                                        }                                                                                                                   \
                                                                                        jh_vector_memmove((_vector1).data + _jh_position + _jh_n, (_vector1).data + _jh_position, sizeof(*(_vector1).data) * ((_vector1).num - _jh_position)); \
                                                                                        (_vector1).num += _jh_n;                                                                                            \
                                                                                        jh_vector_memcpy((_vector1).data + _jh_position, (_vector2).data + _jh_first, sizeof(*(_vector2).data) * _jh_n);    \
                                                                                    } else {                                                                                                                \
                                                                                        if (_jh_position + _jh_n > (_vector1).capacity) {                                                                   \
                                                                                            jh_vector_interior_reserve((_vector1), (_jh_position + _jh_n));                                                 \
                                                                                        }                                                                                                                   \
                                                                                        (_vector1).num = _jh_position + _jh_n;                                                                              \
                                                                                        jh_vector_memcpy((_vector1).data + _jh_position, (_vector2).data + _jh_first, sizeof(*(_vector2).data) * _jh_n);    \
                                                                                    }                                                                                                                       \
                                                                                }                                                                                                                           \
                                                                            } while(0)

#define jh_vector_insert(...) JH_VECTOR_CONCATENATEL(jh_vector_insert_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_erase_2(_vector, _position)   do {                                                                    \
                                                    size_t _jh_position = (_position);                                  \
                                                    if(_jh_position < (_vector).num) {                                  \
                                                        jh_vector_memmove((_vector).data + _jh_position, (_vector).data + _jh_position + 1, sizeof(*(_vector).data) * (((_vector).num--) - _jh_position - 1));\
                                                    }                                                                   \
                                                } while(0)
#define jh_vector_erase_3(_vector, _first, _last)   do {                                                                \
                                                        size_t _jh_first = (_first), _jh_last = (_last);                \
                                                        if(_jh_first < (_vector).num && _jh_first < _jh_last) {         \
                                                            (_vector).num = _jh_last >= (_vector).num ? _jh_first :     \
                                                            (jh_vector_memmove((_vector).data + _jh_first, (_vector).data + _jh_last, sizeof(*(_vector).data) * ((_vector).num - _jh_last)), (_vector).num - _jh_last + _jh_first); \
                                                        }                                                               \
                                                    } while(0)
#define jh_vector_erase(...) JH_VECTOR_CONCATENATEL(jh_vector_erase_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_erase_num(_vector, _n)    do {                                                                    \
                                                size_t _jh_n = (_n);                                                \
                                                (_vector).num = _jh_n > (_vector).num ? 0 : (_vector).num - _jh_n;  \
                                            } while(0)
#define jh_vector_erase_begin(_vector, _begin)  do {                                                                        \
                                                    size_t _jh_begin = (_begin);                                            \
                                                    (_vector).num = _jh_begin > (_vector).num ? (_vector).num : _jh_begin;  \
                                                } while(0)

#define jh_vector_remove(_vector, _first, _last, _value)    ({                                                                  \
                                                                size_t _jh_first = (_first), _jh_last = (_last);                \
                                                                size_t _jh_i, _jh_cursor = _jh_first;                           \
                                                                _jh_last = _jh_last > (_vector).num ? (_vector).num : _jh_last; \
                                                                for(_jh_i = _jh_first; _jh_i < _jh_last; _jh_i++) {             \
                                                                    if((_vector).data[_jh_i] != (_value)) {                     \
                                                                        (_vector).data[_jh_cursor++] = (_vector).data[_jh_i];   \
                                                                    }                                                           \
                                                                }                                                               \
                                                                _jh_cursor;                                                     \
                                                            })

#define jh_vector_unique(_vector, _first, _last)    ({                                                                  \
                                                        size_t _jh_first = (_first), _jh_last = (_last);                \
                                                        int _jh_i, _jh_cursor = _jh_first;                              \
                                                        _jh_last = _jh_last > (_vector).num ? (_vector).num : _jh_last; \
                                                        for(_jh_i = _jh_first + 1; _jh_i < _jh_last; _jh_i++) {         \
                                                            if((_vector).data[_jh_cursor] != (_vector).data[_jh_i]) {   \
                                                                (_vector).data[++_jh_cursor] = (_vector).data[_jh_i];   \
                                                            }                                                           \
                                                        }                                                               \
                                                        _jh_cursor + 1;                                                 \
                                                    })

#define jh_vector_copy_2(_vector1, _vector2)    do {                                                                                                \
                                                    if((_vector1).capacity < (_vector2).num) {                                                      \
                                                        jh_vector_interior_reserve((_vector1), ((_vector2).num));                                   \
                                                    }                                                                                               \
                                                    jh_vector_memcpy((_vector1).data, (_vector2).data, sizeof(*(_vector2).data) * (_vector2).num);  \
                                                    (_vector1).num = (_vector1).num > (_vector2).num ? (_vector1).num : (_vector2).num;             \
                                                } while(0)
#define jh_vector_copy_3(_vector1, _vector2, _n)    do {                                                                                        \
                                                        size_t _jh_n = (_n);                                                                    \
                                                        _jh_n = _jh_n < (_vector2).num ? _jh_n : (_vector2).num;                                \
                                                        if((_vector1).capacity < _jh_n) {                                                       \
                                                            jh_vector_interior_reserve((_vector1), (_jh_n));                                    \
                                                        }                                                                                       \
                                                        jh_vector_memcpy((_vector1).data, (_vector2).data, sizeof(*(_vector2).data) * _jh_n);   \
                                                        (_vector1).num = (_vector1).num > _jh_n ? (_vector1).num : _jh_n;                       \
                                                    } while(0)
#define jh_vector_copy_4(_vector1, _vector2, _first, _last) do {                                                                                                                                \
                                                                size_t _jh_first = (_first), _jh_last = (_last), _jh_n;                                                                         \
                                                                if(_jh_first < _jh_last) {                                                                                                      \
                                                                    _jh_n = _jh_first < (_vector2).num ? (_jh_last > (_vector2).num ? (_vector2).num - _jh_first : _jh_last - _jh_first) : 0;   \
                                                                    if((_vector1).capacity < _jh_n) {                                                                                           \
                                                                        jh_vector_interior_reserve((_vector1), (_jh_n));                                                                        \
                                                                    }                                                                                                                           \
                                                                    jh_vector_memcpy((_vector1).data, (_vector2).data + _jh_first, sizeof(*(_vector2).data) * _jh_n);                           \
                                                                    (_vector1).num = (_vector1).num > _jh_n ? (_vector1).num : _jh_n;                                                           \
                                                                }                                                                                                                               \
                                                            } while(0)
#define jh_vector_copy_5(_vector1, _position, _vector2, _first, _last)  do {                                                                                                                                \
                                                                            size_t _jh_first = (_first), _jh_last = (_last), _jh_position = (_position), _jh_n;                                             \
                                                                            if(_jh_first < _jh_last) {                                                                                                      \
                                                                                _jh_n = _jh_first < (_vector2).num ? (_jh_last > (_vector2).num ? (_vector2).num - _jh_first : _jh_last - _jh_first) : 0;   \
                                                                                if((_vector1).capacity < (_jh_position + _jh_n)) {                                                                          \
                                                                                    jh_vector_interior_reserve((_vector1), (_jh_position + _jh_n));                                                         \
                                                                                }                                                                                                                           \
                                                                                jh_vector_memcpy((_vector1).data + _jh_position, (_vector2).data + _jh_first, sizeof(*(_vector2).data) * _jh_n);            \
                                                                                (_vector1).num = (_jh_position + _jh_n) > (_vector1).num ? (_jh_position + _jh_n) : (_vector1).num;                         \
                                                                            }                                                                                                                               \
                                                                        } while(0)
#define jh_vector_copy(...) JH_VECTOR_CONCATENATEL(jh_vector_copy_, JH_VECTOR_COUNT_ARGS(__VA_ARGS__)) (__VA_ARGS__)

#define jh_vector_sort(_vector, _sort, _compare) ((_sort)((_vector).data, (_vector).num, sizeof(*(_vector).data), (_compare)))

#define jh_vector_shrink_to_fit(_vector) ((_vector).capacity = (_vector).num, (_vector).capacity = jh_vector_roundup_pow_of_two((_vector).capacity), (_vector).data = jh_vector_realloc((_vector).data, sizeof(*(_vector).data) * (_vector).capacity))

#define jh_vector_swap(_vector1, _vector2)  do {                                                                                                            \
                                                void *_jh_data = (_vector1).data; (_vector1).data = (_vector2).data; (_vector2).data = _jh_data;            \
                                                size_t _jh_tmp = (_vector1).num; (_vector1).num = (_vector2).num; (_vector2).num = _jh_tmp;                 \
                                                _jh_tmp = (_vector1).capacity; (_vector1).capacity = (_vector2).capacity; (_vector2).capacity = _jh_tmp;    \
                                            } while(0)

#endif